#include <stdint.h>
#include <stdbool.h>

/**
 * @brief RSA密钥生成算法
 * 
 * @param n 随机选取的两个大素数的乘积，n = p * q
 * @param e 生成的第一把密钥
 * @param d 生成的第二把密钥
*/
void keygen(uint64_t *n, uint64_t *e, uint64_t *d);

/**
 * @brief 随机生成多个字节
 * 
 * @param bytes 用以存储生成的字节
 * @param num 字节的数量
 * 
 * @note 使用之前请确保不会数组越界
*/
void random(void *bytes, int num);

/**
 * @brief 随机选取一个大素数
 * 
 * @return 2^16 <= p < 2^32
*/
uint32_t big_prime();

/**
 * @brief Miller-Rabin算法，用于快速判断一个大数是否是素数
 * 
 * @param n 需要判断是否是素数的数
 * 
 * @note 只要不成立，那么`n`一定是合数。
 * @note 如果成立，那么`n`很可能是素数，但是有极小概率是一个合数
 * @note 时间复杂度 O(log(`n`))
*/
bool miller_rabin_is_prime(uint64_t n);

/**
 * @brief Miller-Rabin算法的一轮
 * 
 * @param n 需要检验是否是素数的数，必须是奇数
 * @param a 用以检验`n`的底数，必须与`n`互素
*/
bool miller_rabin_test(uint64_t n, uint64_t a);

/**
 * @brief 模幂运算，`b`^`e` mod `m`
 * 
 * @param b 底数
 * @param e 指数
 * @param m 模数，不能为0
 * 
 * @note 时间复杂度 O(log(`e`))
*/
uint64_t mod_exp(uint64_t b, uint64_t e, uint64_t m);

/**
 * @brief 模乘运算，`a`*`b` mod `m`
*/
uint64_t mod_mul(uint64_t a, uint64_t b, uint64_t m);

/**
 * @brief 模加运算，`a`+`b` mod `m`
*/
uint64_t mod_add(uint64_t a, uint64_t b, uint64_t m);

/**
 * @brief 欧几里得算法（辗转相除法）
 * 
 * @note 求解两个正整数`a`和`b`的最大公约数（GCD）
*/
uint64_t gcd(uint64_t a, uint64_t b);

/**
 * @brief 拓展欧几里得算法
 * 
 * @note 求解两个正整数`a`和`b`的最大公约数（GCD）
 * @note 并且找到一组整数`x`和`y`，使得`a`*`x` + `b`*`y` = gcd(`a`, `b`)
 * @note 这组解有个特点：|`x`| <= `b` 并且 |`y`| <= `a` 并且 `x`和`y`的符号相反（或者其一为0）
 * @note 使用之前请确保`x`和`y`不会溢出
*/
uint64_t extended_gcd(uint64_t a, uint64_t b, int64_t *x, int64_t *y);

/**
 * @brief 求模逆元，`a` * `x` ≡ 1 (mod `b`)
 * 
 * @param a 与`b`互素
 * @param b 模数，不能为0
 * 
 * @return `x`是最小正整数解
*/
uint64_t mod_mul_inv(uint64_t a, uint64_t b);

/**
 * @brief RSA加密算法
 * 
 * @param m 明文
 * @param e 密钥
 * @param n 两个大素数的乘积，n = p * q
 * 
 * @return 加密之后的`m`
 * 
 * @note `m`必须小于`n`
*/
uint64_t encrypt(uint64_t m, uint64_t e, uint64_t n);

/**
 * @brief RSA解密算法
 * 
 * @param c 密文
 * @param d 密钥
 * @param n 两个大素数的乘积，n = p * q
 * 
 * @return 解密之后的`c`
*/
uint64_t decrypt(uint64_t c, uint64_t d, uint64_t n);